1 Why k-POD?


1.1 K-means drawback


One of the most common clustering algorithms used by data scientists today is k-means clustering. K-means clustering is an easy-to-follow and fast-to-execute algorithm to fulfill basic clustering needs with a simple function call, kmeans().

However, k-means suffers one major drawback : it requires a complete data set without missing entries. Realistically, in many data analysis scenarios, data sets tend to have missing entries due to errors in data collection or data cleaning. When attempting to perform k-means clustering on data sets with missing entries, one faces the following options before proceeding to the clustering:


  1. eliminate the observations(rows) with missing features(columns) from the data set, then perform k-means clustering on partial data;

  2. impute the missing values using a certain algorithm, then perform k-means clustering on imputed data;

  3. contact the data collecting agency for clarification on the missing values.


1.2 K-POD prevails


All these options are either computationally expensive, or lacking competence in producing the ideal clustering results. The kpodcluster package’s kpod() offers an simple, reliable and fast alternative to resolve the difficulties of applying k-means clustering on incomplete data.

In addition to resolving the incomplete data issue, kpod() users have the default option to use the k-means++ algorithm to initialize centers, in order to address the potentially inconsistent clustering results caused by randomized initial centers in k-means clustering.


2 Example Data


2.1 makeData()


kpodclustr includes a makeData() function that generates data sets with missing entries under user’s customization. It produces a list object consisting of 3 objects:


  • Orig : the complete data set.

  • Missing : the incomplete data set.

  • truth : the cluster assignment matrix.


For the remainder of the demonstration of kpodcluster, we will use the example data generated from the following code.

library(kpodclustr)
testData <- kpodclustr::makeData(p = 2, n = 20, k = 5, sigma = 0.25, missing = 0.3, seed = 1991); testData
$Orig
             [,1]        [,2]
 [1,]  0.48131595  2.07241588
 [2,]  1.25157872  2.39232263
 [3,] -2.10800794 -2.67134492
 [4,] -0.90772298  0.08765225
 [5,] -1.74234952 -2.47036381
 [6,]  1.02252072  1.61156947
 [7,]  0.96429404 -0.05556713
 [8,] -0.09799132  1.62825577
 [9,] -2.02722780 -2.77928152
[10,]  1.45909284  2.26439177
[11,]  0.57292135  1.59915187
[12,]  0.50730488  1.58773880
[13,]  0.67676322 -0.38772386
[14,] -2.58590236 -2.83646532
[15,] -2.47255735 -3.26428504
[16,]  0.81804312  1.80383793
[17,]  0.03193879  0.87157793
[18,] -0.70598295  0.89455080
[19,] -0.88524474  0.18824658
[20,]  1.18241623  2.63323410

$Missing
             [,1]        [,2]
 [1,]          NA  2.07241588
 [2,]  1.25157872  2.39232263
 [3,]          NA -2.67134492
 [4,]          NA  0.08765225
 [5,] -1.74234952 -2.47036381
 [6,]  1.02252072  1.61156947
 [7,]          NA -0.05556713
 [8,] -0.09799132          NA
 [9,] -2.02722780          NA
[10,]  1.45909284  2.26439177
[11,]  0.57292135  1.59915187
[12,]  0.50730488  1.58773880
[13,]          NA -0.38772386
[14,]          NA -2.83646532
[15,] -2.47255735 -3.26428504
[16,]  0.81804312  1.80383793
[17,]          NA  0.87157793
[18,] -0.70598295  0.89455080
[19,]          NA  0.18824658
[20,]  1.18241623          NA

$truth
 [1] 4 4 2 1 2 4 3 5 2 4 4 4 3 2 2 4 5 5 1 4

2.2 Parameters example:


  • n = 20 (20 observations)

  • p = 2 (each observation has 2 features)

  • k = 5 (5 clusters, 5 centroids)

  • sigma = 0.25 (scalar of variance for noise around the centroids)

  • missing = 0.3 (missingness, or percentage of missing entries. 20 * 2 * 0.3 = 12 missing entries)

  • seed = 1991 (random seed for reproducibility)


2.3 Process of makeData():


  1. Generate centroid matrix, M, with k*p random samples from standard normal distribution.

  2. Generate assignment matrix, assignment, with n ramdom samples from 1 to k with replacement.

  3. Initialize complete data matrix, X, using M and assignment, so that each observation of X has the same features as its assigned cluster centroid.

  4. Add noise to each value in the initialized X with standard normal distribution multiplying a deviation scalar of sigma.

  5. Initialize incomplete data matrix, X_missing, as a copy of X.

  6. Generate indices of missing entries, missing_ix, with n*p*missing random samples from 1 to n*p without replacement.

  7. Replace values in X_missing at missing_ix indices with NA.

  8. Return X, X_missing, and assignment.


3 Usage of k-POD


3.1 On example data


The key function in kpodclustr is kpod(). kpod() delegates to the rest of the functions in kpodclustr. Like kmeans(), kpod() has a data set parameter, and a number-of-clusters parameter. The difference is that kpod() takes in a incomplete data set. The following code and output displays the usage of kpod() on the second object in the Example Data list, X_missing.

kpodclustr::kpod(X = testData[[2]], k = 5)
$cluster
 [1] 2 5 1 3 1 2 3 3 4 5 2 2 3 1 1 2 3 4 3 3

$cluster_list
$cluster_list[[1]]
 [1] 2 5 1 3 1 5 3 3 4 5 2 2 3 1 1 5 2 4 3 3

$cluster_list[[2]]
 [1] 2 5 1 3 1 2 3 3 4 5 2 2 3 1 1 2 3 4 3 3

$cluster_list[[3]]
 [1] 2 5 1 3 1 2 3 3 4 5 2 2 3 1 1 2 3 4 3 3


$obj_vals
[1] 6.760327 4.292230 3.732434

$fit
[1] 0.9545525

$fit_list
[1] 0.8806050 0.9383399 0.9545525

3.2 Returned items explained


  • cluster : The final cluster assignment matrix containing a sequence of cluster labels corresponding to each observation.

  • cluster_list : A list of cluster assignment matrices throughout all iterations until clustering converges or kpod() reaches maximum iterations. If clustering converges, the last two cluster assignment matrices should be the same. cluster is the last object in cluster_list.

  • obj_vals : The calculated value of the k-means objective function throughout iterations. The k-means objective function measures the sum of all “intra-cluster variance”, or “within-cluster sum of square”, which is the sum of squared distance between each observation and its cluster center for all observations. K-means aims to minimize this intra-cluster variance. As shown in the example output, the objective function value decreases as k-POD clustering progresses.

  • fit : The final measurement of fit of cluster assignment after clustering commences. The closer the fit is to 1, the better the fit. The fit equation is explained below this section.

  • fit_list : A list of measurement of fit of cluster assignment throughout all iterations until clustering converges or kpod() reaches maximum iterations. fit is the last object in fit_list. As shown in the example output, the fit increases and approaches 1 as k-POD clustering progresses.


3.3 The fit equation


\(fit = 1 - ((\sum withinss) / (totss))\)

As mentioned in explanation of obj_vals, “withinss” means “within-cluster sum of square”, which is the sum of squared distance between each observation and its cluster center for each cluster. Taking the sum of “withinss” yields the sum of squared distance between each observation and its cluster center for all clusters.

There is also “betweenss”, meaning “between-cluster sum of square” or “inter-cluster variance”, is the sum of squared distance between all cluster centroids.

“totss”, meaning “total sum of square”, is the sum of squared distance between each observation and the global center(the center of all observations).

A related identity:


\(totss = \sum withinss + betweenss\)

4 k-means vs k-POD


The k-POD method builds upon k-means clustering to provide a simple and quick alternative to clustering missing data that works even when the missingness mechanism is unknown, when external information is unavailable, and when there is significant missingness in the data. — “k-POD: A Method for k-Means Clustering of Missing Data” by Jocelyn T. Chi, Eric C. Chi & Richard G. Baraniuk


4.1 Performance analysis


4.1.1 Metrics


In this clustering performance comparison between k-means and k-POD, we will focus on 2 metrics: fit and Adjusted Rand Index (ARI).

The fit metric is explained under “Usage of k-POD”.

The ARI metric is a measure of similarity between 2 data clusterings. The maximum ARI is 1, meaning the 2 clustering results are the same. The lower the ARI, the greater the difference between 2 data clusterings. The “adjusted” aspect takes into account the permutations of cluster labels. For example, clustering result [1,2,3,3,1] is the same as [2,3,1,1,3]. Therefore, the ARI between those two clusterings is 1.

Before You Continue: The scatter plots for k-POD performance will include all observations in the complete data, because the point of k-POD is to perform clustering on all the observations without eliminating the observations with missing features. However, in k-POD, those missing features will be assigned values and updated throughout iterations, which are not likely the same values as the ones in the complete data.


4.1.2 Data 1


Data 1 parameters: p = 2, n = 20, k = 3, sigma = 0.25, seed = 1991

Data 1 is a relatively small data set (20 observations). We will be looking at:

  • k-means performance with 0% missing;

  • k-POD performance with 10% missing;

  • k-POD performance with 20% missing;

  • k-POD performance with 30% missing;

  • k-POD performance with 40% missing;

  • and k-POD performance with 50% missing.

They are demonstrated by the following scatter plots, colored by cluster group. Black dots in the k-means plot represents the cluster centers.


library(ggplot2)
data1 <- kpodclustr::makeData(p = 2, n = 20, k = 3, sigma = 0.25, missing = 0.1, seed = 1991)
X1991 <- data1[[1]]
km1991 <- kmeans(X1991,3)
fit_km1991 <- 1-(sum(km1991$withinss)/km1991$totss)

g1991means <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(km1991$cluster))) + geom_point() + theme(legend.position = "none") 
g1991means <- g1991means + geom_point(data = as.data.frame(km1991$centers), mapping = aes(x=km1991$centers[,1],y=km1991$centers[,2],size = 3), color = "black")
g1991means <- g1991means + labs(x = "Feature 1", y = "Feature 2", title = "Data 1, k-means with complete data")
g1991means 

Xm1991 <- data1[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991 <- rep(0,5)
fit_kp1991[1] <- kp1991$fit

library(fossil)
ari_kp1991 <- rep(0,5)
ari_kp1991[1] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 1, k-POD with 10% missingness")
g1991pod

data1 <- kpodclustr::makeData(p = 2, n = 20, k = 3, sigma = 0.25, missing = 0.2, seed = 1991)

Xm1991 <- data1[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[2] <- kp1991$fit
ari_kp1991[2] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 1, k-POD with 20% missingness")
g1991pod

data1 <- kpodclustr::makeData(p = 2, n = 20, k = 3, sigma = 0.25, missing = 0.3, seed = 1991)
Xm1991 <- data1[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[3] <- kp1991$fit
ari_kp1991[3] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 1, k-POD with 30% missingness")
g1991pod

data1 <- kpodclustr::makeData(p = 2, n = 20, k = 3, sigma = 0.25, missing = 0.4, seed = 1991)

Xm1991 <- data1[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[4] <- kp1991$fit
ari_kp1991[4] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 1, k-POD with 40% missingness")
g1991pod

data1 <- kpodclustr::makeData(p = 2, n = 20, k = 3, sigma = 0.25, missing = 0.5, seed = 1991)

Xm1991 <- data1[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[5] <- kp1991$fit
ari_kp1991[5] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 1, k-POD with 50% missingness")
g1991pod


The first line graph demonstrates the change in fit value as missingness changes. The blue line represents the fit of the k-means clustering.

The second line graph demonstrates the change in ARI value as missingness changes.

missingpcts <- c(0.1,0.2,0.3,0.4,0.5)
metrics_list <- cbind(missingpcts,fit_kp1991,ari_kp1991)

g1991podfit <- ggplot(data = as.data.frame(metrics_list), mapping = aes(x=missingpcts,y=fit_kp1991)) + geom_line() + geom_point() + geom_label(aes(label = round(fit_kp1991,4)), nudge_y = -0.1)
g1991podfit <- g1991podfit + geom_hline(mapping = aes(yintercept = fit_km1991), color = "blue")
g1991podfit <- g1991podfit + labs(x = "Missingness", y = "Fit") + ylim(0,1)
g1991podfit


g1991podari <- ggplot(data = as.data.frame(metrics_list), mapping = aes(x=missingpcts,y=ari_kp1991)) + geom_line() + geom_point() + geom_label(aes(label = round(ari_kp1991,4)), nudge_y = -0.1)
g1991podari <- g1991podari + labs(x = "Missingness", y = "ARI") + ylim(0,1)
g1991podari


4.1.3 Data 2


Data 2 parameters: p = 2, n = 1000, k = 3, sigma = 0.25, seed = 1991

Data 2 is a larger data set (1000 observations) than Data 1. We will be looking at:

  • k-means performance with 0% missing;

  • k-POD performance with 10% missing;

  • k-POD performance with 20% missing;

  • k-POD performance with 30% missing;

  • k-POD performance with 40% missing;

  • and k-POD performance with 50% missing.

They are demonstrated by the following scatter plots, colored by cluster group. Black dots in the k-means plot represents the cluster centers.


data2 <- kpodclustr::makeData(p = 2, n = 1000, k = 3, sigma = 0.25, missing = 0.1, seed = 1991)
X1991 <- data2[[1]]
km1991 <- kmeans(X1991,3)

fit_km1991 <- 1-(sum(km1991$withinss)/km1991$totss)

g1991means <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(km1991$cluster))) + geom_point() + theme(legend.position = "none") 
g1991means <- g1991means + geom_point(data = as.data.frame(km1991$centers), mapping = aes(x=km1991$centers[,1],y=km1991$centers[,2], size = 3), color = "black")
g1991means <- g1991means + labs(x = "Feature 1", y = "Feature 2", title = "Data 2, k-means with complete data")
g1991means 


Comment: This example happens to demonstrate the inconsistencies in k-means clustering!


Xm1991 <- data2[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991 <- rep(0,5)
fit_kp1991[1] <- kp1991$fit

ari_kp1991 <- rep(0,5)
ari_kp1991[1] <- adj.rand.index(km1991$cluster, kp1991$cluster)
g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 2, k-POD with 10% missingness")
g1991pod

data2 <- kpodclustr::makeData(p = 2, n = 1000, k = 3, sigma = 0.25, missing = 0.2, seed = 1991)

Xm1991 <- data2[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[2] <- kp1991$fit
ari_kp1991[2] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 2, k-POD with 20% missingness")
g1991pod

data2 <- kpodclustr::makeData(p = 2, n = 1000, k = 3, sigma = 0.25, missing = 0.3, seed = 1991)
Xm1991 <- data2[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[3] <- kp1991$fit
ari_kp1991[3] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 2, k-POD with 30% missingness")
g1991pod

data2 <- kpodclustr::makeData(p = 2, n = 1000, k = 3, sigma = 0.25, missing = 0.4, seed = 1991)

Xm1991 <- data2[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[4] <- kp1991$fit
ari_kp1991[4] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 2, k-POD with 40% missingness")
g1991pod

data2 <- kpodclustr::makeData(p = 2, n = 1000, k = 3, sigma = 0.25, missing = 0.5, seed = 1991)

Xm1991 <- data2[[2]]
kp1991 <- kpodclustr::kpod(Xm1991,3)

fit_kp1991[5] <- kp1991$fit
ari_kp1991[5] <- adj.rand.index(km1991$cluster, kp1991$cluster)

g1991pod <- ggplot(data = as.data.frame(X1991), mapping = aes(x=X1991[,1],y=X1991[,2], color=factor(kp1991$cluster))) + geom_point() + theme(legend.position = "none")
g1991pod <- g1991pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 2, k-POD with 50% missingness")
g1991pod


The first line graph demonstrates the change in fit value as missingness changes. The blue line represents the fit of the k-means clustering.

The second line graph demonstrates the change in ARI value as missingness changes.


missingpcts <- c(0.1,0.2,0.3,0.4,0.5)
metrics_list <- cbind(missingpcts,fit_kp1991,ari_kp1991)

g1991podfit <- ggplot(data = as.data.frame(metrics_list), mapping = aes(x=missingpcts,y=fit_kp1991)) + geom_line() + geom_point() + geom_label(aes(label = round(fit_kp1991,4)), nudge_y = -0.1)
g1991podfit <- g1991podfit + geom_hline(mapping = aes(yintercept = fit_km1991), color = "blue")
g1991podfit <- g1991podfit + labs(x = "Missingness", y = "Fit") + ylim(0,1)
g1991podfit


g1991podari <- ggplot(data = as.data.frame(metrics_list), mapping = aes(x=missingpcts,y=ari_kp1991)) + geom_line() + geom_point() + geom_label(aes(label = round(ari_kp1991,4)), nudge_y = -0.1)
g1991podari <- g1991podari + labs(x = "Missingness", y = "ARI") + ylim(0,1)
g1991podari


Comment: Because of the inconsistent k-means clustering, we have a low fit score for the k-means clustering (blue line). We also have low ARI scores because of the drastic difference between the k-means clustering and the k-POD clusterings.


4.1.4 Data 3


Data 3 parameters: p = 2, n = 2000, k = 5, sigma = 0.25, seed = 1992

Data 3 (2000 observations) is twice the size of Data 2 and observations are clustered into 5 clusters, instead of 3. The change sigma signifies an increase in the spread of observations around its cluster center.


data3 <- kpodclustr::makeData(p = 2, n = 2000, k = 5, sigma = 0.5, missing = 0.1, seed = 1992)
X1992 <- data3[[1]]
km1992 <- kmeans(X1992,5)

fit_km1992 <- 1-(sum(km1992$withinss)/km1992$totss)

g1992means <- ggplot(data = as.data.frame(X1992), mapping = aes(x=X1992[,1],y=X1992[,2], color=factor(km1992$cluster))) + geom_point() + theme(legend.position = "none") 
g1992means <- g1992means + geom_point(data = as.data.frame(km1992$centers), mapping = aes(x=km1992$centers[,1],y=km1992$centers[,2], size = 3), color = "black")
g1992means <- g1992means + labs(x = "Feature 1", y = "Feature 2", title = "Data 3, k-means with complete data")
g1992means 

Xm1992 <- data3[[2]]
kp1992 <- kpodclustr::kpod(Xm1992,5)

fit_kp1992 <- rep(0,5)
fit_kp1992[1] <- kp1992$fit

ari_kp1992 <- rep(0,5)
ari_kp1992[1] <- adj.rand.index(km1992$cluster, kp1992$cluster)
g1992pod <- ggplot(data = as.data.frame(X1992), mapping = aes(x=X1992[,1],y=X1992[,2], color=factor(kp1992$cluster))) + geom_point() + theme(legend.position = "none")
g1992pod <- g1992pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 3, k-POD with 10% missingness")
g1992pod

data3 <- kpodclustr::makeData(p = 2, n = 2000, k = 5, sigma = 0.25, missing = 0.2, seed = 1992)

Xm1992 <- data3[[2]]
kp1992 <- kpodclustr::kpod(Xm1992,5)

fit_kp1992[2] <- kp1992$fit
ari_kp1992[2] <- adj.rand.index(km1992$cluster, kp1992$cluster)

g1992pod <- ggplot(data = as.data.frame(X1992), mapping = aes(x=X1992[,1],y=X1992[,2], color=factor(kp1992$cluster))) + geom_point() + theme(legend.position = "none")
g1992pod <- g1992pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 3, k-POD with 20% missingness")
g1992pod

data3 <- kpodclustr::makeData(p = 2, n = 2000, k = 5, sigma = 0.25, missing = 0.3, seed = 1992)

Xm1992 <- data3[[2]]
kp1992 <- kpodclustr::kpod(Xm1992,5)

fit_kp1992[3] <- kp1992$fit
ari_kp1992[3] <- adj.rand.index(km1992$cluster, kp1992$cluster)

g1992pod <- ggplot(data = as.data.frame(X1992), mapping = aes(x=X1992[,1],y=X1992[,2], color=factor(kp1992$cluster))) + geom_point() + theme(legend.position = "none")
g1992pod <- g1992pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 3, k-POD with 30% missingness")
g1992pod

data3 <- kpodclustr::makeData(p = 2, n = 2000, k = 5, sigma = 0.25, missing = 0.4, seed = 1992)

Xm1992 <- data3[[2]]
kp1992 <- kpodclustr::kpod(Xm1992,5)

fit_kp1992[4] <- kp1992$fit
ari_kp1992[4] <- adj.rand.index(km1992$cluster, kp1992$cluster)

g1992pod <- ggplot(data = as.data.frame(X1992), mapping = aes(x=X1992[,1],y=X1992[,2], color=factor(kp1992$cluster))) + geom_point() + theme(legend.position = "none")
g1992pod <- g1992pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 3, k-POD with 40% missingness")
g1992pod

data3 <- kpodclustr::makeData(p = 2, n = 2000, k = 5, sigma = 0.25, missing = 0.5, seed = 1992)

Xm1992 <- data3[[2]]
kp1992 <- kpodclustr::kpod(Xm1992,5)

fit_kp1992[5] <- kp1992$fit
ari_kp1992[5] <- adj.rand.index(km1992$cluster, kp1992$cluster)

g1992pod <- ggplot(data = as.data.frame(X1992), mapping = aes(x=X1992[,1],y=X1992[,2], color=factor(kp1992$cluster))) + geom_point() + theme(legend.position = "none")
g1992pod <- g1992pod + labs(x = "Feature 1", y = "Feature 2", title = "Data 3, k-POD with 50% missingness")
g1992pod


The first line graph demonstrates the change in fit value as missingness changes. The blue line represents the fit of the k-means clustering.

The second line graph demonstrates the change in ARI value as missingness changes.


missingpcts <- c(0.1,0.2,0.3,0.4,0.5)
metrics_list <- cbind(missingpcts,fit_kp1992,ari_kp1992)

g1992podfit <- ggplot(data = as.data.frame(metrics_list), mapping = aes(x=missingpcts,y=fit_kp1992)) + geom_line() + geom_point() + geom_label(aes(label = round(fit_kp1992,4)), nudge_y = 0.05)
g1992podfit <- g1992podfit + geom_hline(mapping = aes(yintercept = fit_km1992), color = "blue")
g1992podfit <- g1992podfit + labs(x = "Missingness", y = "Fit") + ylim(0,1)
g1992podfit


g1992podari <- ggplot(data = as.data.frame(metrics_list), mapping = aes(x=missingpcts,y=ari_kp1992)) + geom_line() + geom_point() + geom_label(aes(label = round(ari_kp1992,4)), nudge_y = -0.1)
g1992podari <- g1992podari + labs(x = "Missingness", y = "ARI") + ylim(0,1)
g1992podari


4.1.5 Plots explained


As previously mentioned, the scatter plots for k-POD performance will include all observations in the complete data like the plots for k-means, because the point of k-POD is to perform clustering on all the observations including those with missing features. However, in k-POD, those missing features will be assigned values and updated throughout iterations, which are not likely the same values as the ones in the complete data. This explains why even though the k-POD clustering scatter plots may look worse than the k-means scatter plot, but k-POD tend to have better values for the fit metric.

From the generated line plots measuring the fit and ARI metrics of k-pod clustering compared to k-means clustering, we can conclude: k-POD is more consistent when data is larger. In addition, when data is larger, it is more obvious that the higher the missingness, the lower the ARI, which means k-POD clustering displays more deviation than k-means clustering as missingness increases. We also notice that k-POD performance is not greatly affected by increasing the missingness within the data.

These performance analysis do not demonstrate k-POD’s fast execution time. Detailed discussion about attributes of k-POD clustering please refer to “k-POD: A Method for k-Means Clustering of Missing Data” by Jocelyn T. Chi, Eric C. Chi & Richard G. Baraniuk.


LS0tCnRpdGxlOiAiSW50cm9kdWN0aW9uIHRvIGtwb2RjbHVzdGVyIgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6CiAgICBjb2RlX2ZvbGRpbmc6IGhpZGUKICAgIHRvYzogdHJ1ZQogICAgdG9jX2Zsb2F0OiB0cnVlCiAgICB0b2NfZGVwdGg6IDQKICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQogICAgdGhlbWU6IHJlYWRhYmxlCiAgICBoaWdobGlnaHQ6IHRhbmdvCiAgICBmaWcud2lkdGg6IDMKICAgIGZpZy5oZWlnaHQ6IDIKLS0tCgoqKioKCiMgV2h5IGstUE9EPwoKKioqCgojIyBLLW1lYW5zIGRyYXdiYWNrCgoqKioKCk9uZSBvZiB0aGUgbW9zdCBjb21tb24gY2x1c3RlcmluZyBhbGdvcml0aG1zIHVzZWQgYnkgZGF0YSBzY2llbnRpc3RzIHRvZGF5IGlzIGstbWVhbnMgY2x1c3RlcmluZy4gSy1tZWFucyBjbHVzdGVyaW5nIGlzIGFuIGVhc3ktdG8tZm9sbG93IGFuZCBmYXN0LXRvLWV4ZWN1dGUgYWxnb3JpdGhtIHRvIGZ1bGZpbGwgYmFzaWMgY2x1c3RlcmluZyBuZWVkcyB3aXRoIGEgc2ltcGxlIGZ1bmN0aW9uIGNhbGwsIGBrbWVhbnMoKWAuIAoKSG93ZXZlciwgay1tZWFucyBzdWZmZXJzIG9uZSBtYWpvciBkcmF3YmFjayA6IGl0IHJlcXVpcmVzIGEgX19jb21wbGV0ZV9fIGRhdGEgc2V0IHdpdGhvdXQgbWlzc2luZyBlbnRyaWVzLiBSZWFsaXN0aWNhbGx5LCBpbiBtYW55IGRhdGEgYW5hbHlzaXMgc2NlbmFyaW9zLCBkYXRhIHNldHMgdGVuZCB0byBoYXZlIG1pc3NpbmcgZW50cmllcyBkdWUgdG8gZXJyb3JzIGluIGRhdGEgY29sbGVjdGlvbiBvciBkYXRhIGNsZWFuaW5nLiBXaGVuIGF0dGVtcHRpbmcgdG8gcGVyZm9ybSBrLW1lYW5zIGNsdXN0ZXJpbmcgb24gZGF0YSBzZXRzIHdpdGggbWlzc2luZyBlbnRyaWVzLCBvbmUgZmFjZXMgdGhlIGZvbGxvd2luZyBvcHRpb25zIGJlZm9yZSBwcm9jZWVkaW5nIHRvIHRoZSBjbHVzdGVyaW5nOgoKKioqCjEuIGVsaW1pbmF0ZSB0aGUgb2JzZXJ2YXRpb25zKHJvd3MpIHdpdGggbWlzc2luZyBmZWF0dXJlcyhjb2x1bW5zKSBmcm9tIHRoZSBkYXRhIHNldCwgdGhlbiBwZXJmb3JtIGstbWVhbnMgY2x1c3RlcmluZyBvbiBwYXJ0aWFsIGRhdGE7CgoyLiBpbXB1dGUgdGhlIG1pc3NpbmcgdmFsdWVzIHVzaW5nIGEgY2VydGFpbiBhbGdvcml0aG0sIHRoZW4gcGVyZm9ybSBrLW1lYW5zIGNsdXN0ZXJpbmcgb24gaW1wdXRlZCBkYXRhOwoKMy4gY29udGFjdCB0aGUgZGF0YSBjb2xsZWN0aW5nIGFnZW5jeSBmb3IgY2xhcmlmaWNhdGlvbiBvbiB0aGUgbWlzc2luZyB2YWx1ZXMuCgoqKioKCiMjIEstUE9EIHByZXZhaWxzCgoqKioKCkFsbCB0aGVzZSBvcHRpb25zIGFyZSBlaXRoZXIgY29tcHV0YXRpb25hbGx5IGV4cGVuc2l2ZSwgb3IgbGFja2luZyBjb21wZXRlbmNlIGluIHByb2R1Y2luZyB0aGUgaWRlYWwgY2x1c3RlcmluZyByZXN1bHRzLiBUaGUgYGtwb2RjbHVzdGVyYCBwYWNrYWdlJ3MgYGtwb2QoKWAgb2ZmZXJzIGFuIHNpbXBsZSwgcmVsaWFibGUgYW5kIGZhc3QgYWx0ZXJuYXRpdmUgdG8gcmVzb2x2ZSB0aGUgZGlmZmljdWx0aWVzIG9mIGFwcGx5aW5nIGstbWVhbnMgY2x1c3RlcmluZyBvbiBfX2luY29tcGxldGVfXyBkYXRhLiAKCkluIGFkZGl0aW9uIHRvIHJlc29sdmluZyB0aGUgaW5jb21wbGV0ZSBkYXRhIGlzc3VlLCBga3BvZCgpYCB1c2VycyBoYXZlIHRoZSBkZWZhdWx0IG9wdGlvbiB0byB1c2UgdGhlIF9fay1tZWFucysrX18gYWxnb3JpdGhtIHRvIGluaXRpYWxpemUgY2VudGVycywgaW4gb3JkZXIgdG8gYWRkcmVzcyB0aGUgcG90ZW50aWFsbHkgaW5jb25zaXN0ZW50IGNsdXN0ZXJpbmcgcmVzdWx0cyBjYXVzZWQgYnkgcmFuZG9taXplZCBpbml0aWFsIGNlbnRlcnMgaW4gay1tZWFucyBjbHVzdGVyaW5nLgoKKioqCgojIEV4YW1wbGUgRGF0YQoKKioqCgojIyBtYWtlRGF0YSgpCgoqKioKCmBrcG9kY2x1c3RyYCBpbmNsdWRlcyBhIGBtYWtlRGF0YSgpYCBmdW5jdGlvbiB0aGF0IGdlbmVyYXRlcyBkYXRhIHNldHMgd2l0aCBtaXNzaW5nIGVudHJpZXMgdW5kZXIgdXNlcidzIGN1c3RvbWl6YXRpb24uIEl0IHByb2R1Y2VzIGEgbGlzdCBvYmplY3QgY29uc2lzdGluZyBvZiAzIG9iamVjdHM6CgoqKioKCi0gYE9yaWdgIDogdGhlIGNvbXBsZXRlIGRhdGEgc2V0LgoKLSBgTWlzc2luZ2AgOiB0aGUgaW5jb21wbGV0ZSBkYXRhIHNldC4gCgotIGB0cnV0aGAgOiB0aGUgY2x1c3RlciBhc3NpZ25tZW50IG1hdHJpeC4gCgoqKioKCkZvciB0aGUgcmVtYWluZGVyIG9mIHRoZSBkZW1vbnN0cmF0aW9uIG9mIGBrcG9kY2x1c3RlcmAsIHdlIHdpbGwgdXNlIHRoZSBleGFtcGxlIGRhdGEgZ2VuZXJhdGVkIGZyb20gdGhlIGZvbGxvd2luZyBjb2RlLiAKCmBgYHtyIGV4YW1wbGVEYXRhLCBjbGFzcy5zb3VyY2UgPSAnZm9sZC1zaG93J30KbGlicmFyeShrcG9kY2x1c3RyKQp0ZXN0RGF0YSA8LSBrcG9kY2x1c3RyOjptYWtlRGF0YShwID0gMiwgbiA9IDIwLCBrID0gNSwgc2lnbWEgPSAwLjI1LCBtaXNzaW5nID0gMC4zLCBzZWVkID0gMTk5MSk7IHRlc3REYXRhCmBgYAoKIyMgUGFyYW1ldGVycyBleGFtcGxlOiAKCioqKgoKLSBuID0gMjAgKDIwIG9ic2VydmF0aW9ucykKCi0gcCA9IDIgKGVhY2ggb2JzZXJ2YXRpb24gaGFzIDIgZmVhdHVyZXMpCgotIGsgPSA1ICg1IGNsdXN0ZXJzLCA1IGNlbnRyb2lkcykgCgotIHNpZ21hID0gMC4yNSAoc2NhbGFyIG9mIHZhcmlhbmNlIGZvciBub2lzZSBhcm91bmQgdGhlIGNlbnRyb2lkcykgCgotIG1pc3NpbmcgPSAwLjMgKG1pc3NpbmduZXNzLCBvciBwZXJjZW50YWdlIG9mIG1pc3NpbmcgZW50cmllcy4gMjAgKiAyICogMC4zID0gMTIgbWlzc2luZyBlbnRyaWVzKQoKLSBzZWVkID0gMTk5MSAocmFuZG9tIHNlZWQgZm9yIHJlcHJvZHVjaWJpbGl0eSkKCioqKgoKIyMgUHJvY2VzcyBvZiBgbWFrZURhdGEoKWA6CgoqKioKCjEuIEdlbmVyYXRlIGNlbnRyb2lkIG1hdHJpeCwgYE1gLCB3aXRoIGBrYCpgcGAgcmFuZG9tIHNhbXBsZXMgZnJvbSBzdGFuZGFyZCBub3JtYWwgZGlzdHJpYnV0aW9uLgoKMi4gR2VuZXJhdGUgYXNzaWdubWVudCBtYXRyaXgsIGBhc3NpZ25tZW50YCwgd2l0aCBgbmAgcmFtZG9tIHNhbXBsZXMgZnJvbSAxIHRvIGBrYCB3aXRoIHJlcGxhY2VtZW50LgoKMy4gSW5pdGlhbGl6ZSBjb21wbGV0ZSBkYXRhIG1hdHJpeCwgYFhgLCB1c2luZyBgTWAgYW5kIGBhc3NpZ25tZW50YCwgc28gdGhhdCBlYWNoIG9ic2VydmF0aW9uIG9mIGBYYCBoYXMgdGhlIHNhbWUgZmVhdHVyZXMgYXMgaXRzIGFzc2lnbmVkIGNsdXN0ZXIgY2VudHJvaWQuCgo0LiBBZGQgbm9pc2UgdG8gZWFjaCB2YWx1ZSBpbiB0aGUgaW5pdGlhbGl6ZWQgYFhgIHdpdGggc3RhbmRhcmQgbm9ybWFsIGRpc3RyaWJ1dGlvbiBtdWx0aXBseWluZyBhIGRldmlhdGlvbiBzY2FsYXIgb2YgYHNpZ21hYC4gCgo1LiBJbml0aWFsaXplIGluY29tcGxldGUgZGF0YSBtYXRyaXgsIGBYX21pc3NpbmdgLCBhcyBhIGNvcHkgb2YgYFhgLgoKNi4gR2VuZXJhdGUgaW5kaWNlcyBvZiBtaXNzaW5nIGVudHJpZXMsIGBtaXNzaW5nX2l4YCwgd2l0aCBgbmBcKmBwYFwqYG1pc3NpbmdgIHJhbmRvbSBzYW1wbGVzIGZyb20gMSB0byBgbmBcKmBwYCB3aXRob3V0IHJlcGxhY2VtZW50LgoKNy4gUmVwbGFjZSB2YWx1ZXMgaW4gYFhfbWlzc2luZ2AgYXQgYG1pc3NpbmdfaXhgIGluZGljZXMgd2l0aCBgTkFgLgoKOC4gUmV0dXJuIGBYYCwgYFhfbWlzc2luZ2AsIGFuZCBgYXNzaWdubWVudGAuCgoqKioKCiMgVXNhZ2Ugb2Ygay1QT0QgCgoqKioKCiMjIE9uIGV4YW1wbGUgZGF0YQoKKioqCgpUaGUgX19rZXkgZnVuY3Rpb25fXyBpbiBga3BvZGNsdXN0cmAgaXMgYGtwb2QoKWAuIGBrcG9kKClgIGRlbGVnYXRlcyB0byB0aGUgcmVzdCBvZiB0aGUgZnVuY3Rpb25zIGluIGBrcG9kY2x1c3RyYC4gTGlrZSBga21lYW5zKClgLCBga3BvZCgpYCBoYXMgYSBkYXRhIHNldCBwYXJhbWV0ZXIsIGFuZCBhIG51bWJlci1vZi1jbHVzdGVycyBwYXJhbWV0ZXIuIFRoZSBkaWZmZXJlbmNlIGlzIHRoYXQgYGtwb2QoKWAgdGFrZXMgaW4gYSBpbmNvbXBsZXRlIGRhdGEgc2V0LiBUaGUgZm9sbG93aW5nIGNvZGUgYW5kIG91dHB1dCBkaXNwbGF5cyB0aGUgdXNhZ2Ugb2YgYGtwb2QoKWAgb24gdGhlIHNlY29uZCBvYmplY3QgaW4gdGhlIEV4YW1wbGUgRGF0YSBsaXN0LCBgWF9taXNzaW5nYC4KCmBgYHtyIGtwb2RVc2FnZSwgY2xhc3Muc291cmNlID0gJ2ZvbGQtc2hvdyd9Cmtwb2RjbHVzdHI6Omtwb2QoWCA9IHRlc3REYXRhW1syXV0sIGsgPSA1KQpgYGAKCiMjIFJldHVybmVkIGl0ZW1zIGV4cGxhaW5lZAoKKioqCgotIGBjbHVzdGVyYCA6IFRoZSBmaW5hbCBjbHVzdGVyIGFzc2lnbm1lbnQgbWF0cml4IGNvbnRhaW5pbmcgYSBzZXF1ZW5jZSBvZiBjbHVzdGVyIGxhYmVscyBjb3JyZXNwb25kaW5nIHRvIGVhY2ggb2JzZXJ2YXRpb24uCgotIGBjbHVzdGVyX2xpc3RgIDogQSBsaXN0IG9mIGNsdXN0ZXIgYXNzaWdubWVudCBtYXRyaWNlcyB0aHJvdWdob3V0IGFsbCBpdGVyYXRpb25zIHVudGlsIGNsdXN0ZXJpbmcgY29udmVyZ2VzIG9yIGBrcG9kKClgIHJlYWNoZXMgbWF4aW11bSBpdGVyYXRpb25zLiBJZiBjbHVzdGVyaW5nIGNvbnZlcmdlcywgdGhlIGxhc3QgdHdvIGNsdXN0ZXIgYXNzaWdubWVudCBtYXRyaWNlcyBzaG91bGQgYmUgdGhlIHNhbWUuIGBjbHVzdGVyYCBpcyB0aGUgbGFzdCBvYmplY3QgaW4gYGNsdXN0ZXJfbGlzdGAuCgotIGBvYmpfdmFsc2AgOiBUaGUgY2FsY3VsYXRlZCB2YWx1ZSBvZiB0aGUgay1tZWFucyBvYmplY3RpdmUgZnVuY3Rpb24gdGhyb3VnaG91dCBpdGVyYXRpb25zLiBUaGUgX19rLW1lYW5zIG9iamVjdGl2ZSBmdW5jdGlvbl9fIG1lYXN1cmVzIHRoZSBzdW0gb2YgYWxsICJpbnRyYS1jbHVzdGVyIHZhcmlhbmNlIiwgb3IgIndpdGhpbi1jbHVzdGVyIHN1bSBvZiBzcXVhcmUiLCB3aGljaCBpcyB0aGUgc3VtIG9mIHNxdWFyZWQgZGlzdGFuY2UgYmV0d2VlbiBlYWNoIG9ic2VydmF0aW9uIGFuZCBpdHMgY2x1c3RlciBjZW50ZXIgZm9yIGFsbCBvYnNlcnZhdGlvbnMuIEstbWVhbnMgYWltcyB0byBtaW5pbWl6ZSB0aGlzIGludHJhLWNsdXN0ZXIgdmFyaWFuY2UuIEFzIHNob3duIGluIHRoZSBleGFtcGxlIG91dHB1dCwgdGhlIG9iamVjdGl2ZSBmdW5jdGlvbiB2YWx1ZSBkZWNyZWFzZXMgYXMgay1QT0QgY2x1c3RlcmluZyBwcm9ncmVzc2VzLiAKCi0gYGZpdGAgOiBUaGUgZmluYWwgbWVhc3VyZW1lbnQgb2YgZml0IG9mIGNsdXN0ZXIgYXNzaWdubWVudCBhZnRlciBjbHVzdGVyaW5nIGNvbW1lbmNlcy4gVGhlIGNsb3NlciB0aGUgZml0IGlzIHRvIDEsIHRoZSBiZXR0ZXIgdGhlIGZpdC4gVGhlIGZpdCBlcXVhdGlvbiBpcyBleHBsYWluZWQgYmVsb3cgdGhpcyBzZWN0aW9uLgoKLSBgZml0X2xpc3RgIDogQSBsaXN0IG9mIG1lYXN1cmVtZW50IG9mIGZpdCBvZiBjbHVzdGVyIGFzc2lnbm1lbnQgdGhyb3VnaG91dCBhbGwgaXRlcmF0aW9ucyB1bnRpbCBjbHVzdGVyaW5nIGNvbnZlcmdlcyBvciBga3BvZCgpYCByZWFjaGVzIG1heGltdW0gaXRlcmF0aW9ucy4gYGZpdGAgaXMgdGhlIGxhc3Qgb2JqZWN0IGluIGBmaXRfbGlzdGAuIEFzIHNob3duIGluIHRoZSBleGFtcGxlIG91dHB1dCwgdGhlIGZpdCBpbmNyZWFzZXMgYW5kIGFwcHJvYWNoZXMgMSBhcyBrLVBPRCBjbHVzdGVyaW5nIHByb2dyZXNzZXMuCgoqKioKCiMjIFRoZSBgZml0YCBlcXVhdGlvbgoKKioqCgo8Y2VudGVyPiAkZml0ID0gMSAtICgoXHN1bSB3aXRoaW5zcykgLyAodG90c3MpKSQgPC9jZW50ZXI+CgoqKioKCkFzIG1lbnRpb25lZCBpbiBleHBsYW5hdGlvbiBvZiBgb2JqX3ZhbHNgLCAid2l0aGluc3MiIG1lYW5zICJ3aXRoaW4tY2x1c3RlciBzdW0gb2Ygc3F1YXJlIiwgd2hpY2ggaXMgdGhlIHN1bSBvZiBzcXVhcmVkIGRpc3RhbmNlIGJldHdlZW4gZWFjaCBvYnNlcnZhdGlvbiBhbmQgaXRzIGNsdXN0ZXIgY2VudGVyIGZvciBlYWNoIGNsdXN0ZXIuIFRha2luZyB0aGUgc3VtIG9mICJ3aXRoaW5zcyIgeWllbGRzIHRoZSBzdW0gb2Ygc3F1YXJlZCBkaXN0YW5jZSBiZXR3ZWVuIGVhY2ggb2JzZXJ2YXRpb24gYW5kIGl0cyBjbHVzdGVyIGNlbnRlciBmb3IgYWxsIGNsdXN0ZXJzLgoKVGhlcmUgaXMgYWxzbyAiYmV0d2VlbnNzIiwgbWVhbmluZyAiYmV0d2Vlbi1jbHVzdGVyIHN1bSBvZiBzcXVhcmUiIG9yICJpbnRlci1jbHVzdGVyIHZhcmlhbmNlIiwgaXMgdGhlIHN1bSBvZiBzcXVhcmVkIGRpc3RhbmNlIGJldHdlZW4gYWxsIGNsdXN0ZXIgY2VudHJvaWRzLiAKCiJ0b3RzcyIsIG1lYW5pbmcgInRvdGFsIHN1bSBvZiBzcXVhcmUiLCBpcyB0aGUgc3VtIG9mIHNxdWFyZWQgZGlzdGFuY2UgYmV0d2VlbiBlYWNoIG9ic2VydmF0aW9uIGFuZCB0aGUgZ2xvYmFsIGNlbnRlcih0aGUgY2VudGVyIG9mIGFsbCBvYnNlcnZhdGlvbnMpLiAKCkEgcmVsYXRlZCBpZGVudGl0eTogCgoqKioKCjxjZW50ZXI+ICR0b3RzcyA9IFxzdW0gd2l0aGluc3MgKyBiZXR3ZWVuc3MkIDwvY2VudGVyPgoKKioqCgojIGstbWVhbnMgdnMgay1QT0QKCioqKgoKPiBUaGUgay1QT0QgbWV0aG9kIGJ1aWxkcyB1cG9uIGstbWVhbnMgY2x1c3RlcmluZyB0byBwcm92aWRlIGEgc2ltcGxlIGFuZCBxdWljayBhbHRlcm5hdGl2ZSB0byBjbHVzdGVyaW5nIG1pc3NpbmcgZGF0YSB0aGF0IHdvcmtzIGV2ZW4gd2hlbiBfdGhlIG1pc3NpbmduZXNzIG1lY2hhbmlzbSBpcyB1bmtub3duXywgd2hlbiBfZXh0ZXJuYWwgaW5mb3JtYXRpb24gaXMgdW5hdmFpbGFibGVfLCBhbmQgd2hlbiBfdGhlcmUgaXMgc2lnbmlmaWNhbnQgbWlzc2luZ25lc3MgaW4gdGhlIGRhdGFfLiAtLS0gImstUE9EOiBBIE1ldGhvZCBmb3Igay1NZWFucyBDbHVzdGVyaW5nIG9mIE1pc3NpbmcgRGF0YSIgYnkgSm9jZWx5biBULiBDaGksIEVyaWMgQy4gQ2hpICYgUmljaGFyZCBHLiBCYXJhbml1awoKKioqCgojIyBQZXJmb3JtYW5jZSBhbmFseXNpcwoKKioqCgojIyMgTWV0cmljcwoKKioqCgpJbiB0aGlzIGNsdXN0ZXJpbmcgcGVyZm9ybWFuY2UgY29tcGFyaXNvbiBiZXR3ZWVuIGstbWVhbnMgYW5kIGstUE9ELCB3ZSB3aWxsIGZvY3VzIG9uIDIgbWV0cmljczogZml0IGFuZCBBZGp1c3RlZCBSYW5kIEluZGV4IChBUkkpLiAKClRoZSBmaXQgbWV0cmljIGlzIGV4cGxhaW5lZCB1bmRlciAiVXNhZ2Ugb2Ygay1QT0QiLiAKClRoZSBBUkkgbWV0cmljIGlzIGEgbWVhc3VyZSBvZiBzaW1pbGFyaXR5IGJldHdlZW4gMiBkYXRhIGNsdXN0ZXJpbmdzLiBUaGUgbWF4aW11bSBBUkkgaXMgMSwgbWVhbmluZyB0aGUgMiBjbHVzdGVyaW5nIHJlc3VsdHMgYXJlIHRoZSBzYW1lLiBUaGUgbG93ZXIgdGhlIEFSSSwgdGhlIGdyZWF0ZXIgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiAyIGRhdGEgY2x1c3RlcmluZ3MuIFRoZSAiYWRqdXN0ZWQiIGFzcGVjdCB0YWtlcyBpbnRvIGFjY291bnQgdGhlIHBlcm11dGF0aW9ucyBvZiBjbHVzdGVyIGxhYmVscy4gRm9yIGV4YW1wbGUsIGNsdXN0ZXJpbmcgcmVzdWx0IFsxLDIsMywzLDFdIGlzIHRoZSBzYW1lIGFzIFsyLDMsMSwxLDNdLiBUaGVyZWZvcmUsIHRoZSBBUkkgYmV0d2VlbiB0aG9zZSB0d28gY2x1c3RlcmluZ3MgaXMgMS4gCgpfX0JlZm9yZSBZb3UgQ29udGludWVfXzogVGhlIHNjYXR0ZXIgcGxvdHMgZm9yIGstUE9EIHBlcmZvcm1hbmNlIHdpbGwgaW5jbHVkZSBhbGwgb2JzZXJ2YXRpb25zIGluIHRoZSBjb21wbGV0ZSBkYXRhLCBiZWNhdXNlIHRoZSBwb2ludCBvZiBrLVBPRCBpcyB0byBwZXJmb3JtIGNsdXN0ZXJpbmcgb24gYWxsIHRoZSBvYnNlcnZhdGlvbnMgd2l0aG91dCBlbGltaW5hdGluZyB0aGUgb2JzZXJ2YXRpb25zIHdpdGggbWlzc2luZyBmZWF0dXJlcy4gSG93ZXZlciwgaW4gay1QT0QsIHRob3NlIG1pc3NpbmcgZmVhdHVyZXMgd2lsbCBiZSBhc3NpZ25lZCB2YWx1ZXMgYW5kIHVwZGF0ZWQgdGhyb3VnaG91dCBpdGVyYXRpb25zLCB3aGljaCBhcmUgbm90IGxpa2VseSB0aGUgc2FtZSB2YWx1ZXMgYXMgdGhlIG9uZXMgaW4gdGhlIGNvbXBsZXRlIGRhdGEuIAoKKioqCgojIyMgRGF0YSAxCgoqKioKCkRhdGEgMSBwYXJhbWV0ZXJzOiBwID0gMiwgbiA9IDIwLCBrID0gMywgc2lnbWEgPSAwLjI1LCBzZWVkID0gMTk5MQoKRGF0YSAxIGlzIGEgcmVsYXRpdmVseSBzbWFsbCBkYXRhIHNldCAoMjAgb2JzZXJ2YXRpb25zKS4gV2Ugd2lsbCBiZSBsb29raW5nIGF0OgoKLSBrLW1lYW5zIHBlcmZvcm1hbmNlIHdpdGggMCUgbWlzc2luZzsgCgotIGstUE9EIHBlcmZvcm1hbmNlIHdpdGggMTAlIG1pc3Npbmc7IAoKLSBrLVBPRCBwZXJmb3JtYW5jZSB3aXRoIDIwJSBtaXNzaW5nOyAKCi0gay1QT0QgcGVyZm9ybWFuY2Ugd2l0aCAzMCUgbWlzc2luZzsgCgotIGstUE9EIHBlcmZvcm1hbmNlIHdpdGggNDAlIG1pc3Npbmc7IAoKLSBhbmQgay1QT0QgcGVyZm9ybWFuY2Ugd2l0aCA1MCUgbWlzc2luZy4KClRoZXkgYXJlIGRlbW9uc3RyYXRlZCBieSB0aGUgZm9sbG93aW5nIHNjYXR0ZXIgcGxvdHMsIGNvbG9yZWQgYnkgY2x1c3RlciBncm91cC4gQmxhY2sgZG90cyBpbiB0aGUgay1tZWFucyBwbG90IHJlcHJlc2VudHMgdGhlIGNsdXN0ZXIgY2VudGVycy4gIAoKKioqCgpgYGB7ciBkYXRhMW1lYW5zLCBvdXQuaGVpZ2h0PSI1MCUiLCBvdXQud2lkdGg9IjUwJSJ9CmxpYnJhcnkoZ2dwbG90MikKZGF0YTEgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAyMCwgayA9IDMsIHNpZ21hID0gMC4yNSwgbWlzc2luZyA9IDAuMSwgc2VlZCA9IDE5OTEpClgxOTkxIDwtIGRhdGExW1sxXV0Ka20xOTkxIDwtIGttZWFucyhYMTk5MSwzKQpmaXRfa20xOTkxIDwtIDEtKHN1bShrbTE5OTEkd2l0aGluc3MpL2ttMTk5MSR0b3RzcykKCmcxOTkxbWVhbnMgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKFgxOTkxKSwgbWFwcGluZyA9IGFlcyh4PVgxOTkxWywxXSx5PVgxOTkxWywyXSwgY29sb3I9ZmFjdG9yKGttMTk5MSRjbHVzdGVyKSkpICsgZ2VvbV9wb2ludCgpICsgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKSAKZzE5OTFtZWFucyA8LSBnMTk5MW1lYW5zICsgZ2VvbV9wb2ludChkYXRhID0gYXMuZGF0YS5mcmFtZShrbTE5OTEkY2VudGVycyksIG1hcHBpbmcgPSBhZXMoeD1rbTE5OTEkY2VudGVyc1ssMV0seT1rbTE5OTEkY2VudGVyc1ssMl0sc2l6ZSA9IDMpLCBjb2xvciA9ICJibGFjayIpCmcxOTkxbWVhbnMgPC0gZzE5OTFtZWFucyArIGxhYnMoeCA9ICJGZWF0dXJlIDEiLCB5ID0gIkZlYXR1cmUgMiIsIHRpdGxlID0gIkRhdGEgMSwgay1tZWFucyB3aXRoIGNvbXBsZXRlIGRhdGEiKQpnMTk5MW1lYW5zIApgYGAKCmBgYHtyIGRhdGExcG9kMC4xfQpYbTE5OTEgPC0gZGF0YTFbWzJdXQprcDE5OTEgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTEsMykKCmZpdF9rcDE5OTEgPC0gcmVwKDAsNSkKZml0X2twMTk5MVsxXSA8LSBrcDE5OTEkZml0CgpsaWJyYXJ5KGZvc3NpbCkKYXJpX2twMTk5MSA8LSByZXAoMCw1KQphcmlfa3AxOTkxWzFdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MSRjbHVzdGVyLCBrcDE5OTEkY2x1c3RlcikKCmcxOTkxcG9kIDwtIGdncGxvdChkYXRhID0gYXMuZGF0YS5mcmFtZShYMTk5MSksIG1hcHBpbmcgPSBhZXMoeD1YMTk5MVssMV0seT1YMTk5MVssMl0sIGNvbG9yPWZhY3RvcihrcDE5OTEkY2x1c3RlcikpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKZzE5OTFwb2QgPC0gZzE5OTFwb2QgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDEsIGstUE9EIHdpdGggMTAlIG1pc3NpbmduZXNzIikKZzE5OTFwb2QKYGBgCgpgYGB7ciBkYXRhMXBvZDAuMn0KZGF0YTEgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAyMCwgayA9IDMsIHNpZ21hID0gMC4yNSwgbWlzc2luZyA9IDAuMiwgc2VlZCA9IDE5OTEpCgpYbTE5OTEgPC0gZGF0YTFbWzJdXQprcDE5OTEgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTEsMykKCmZpdF9rcDE5OTFbMl0gPC0ga3AxOTkxJGZpdAphcmlfa3AxOTkxWzJdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MSRjbHVzdGVyLCBrcDE5OTEkY2x1c3RlcikKCmcxOTkxcG9kIDwtIGdncGxvdChkYXRhID0gYXMuZGF0YS5mcmFtZShYMTk5MSksIG1hcHBpbmcgPSBhZXMoeD1YMTk5MVssMV0seT1YMTk5MVssMl0sIGNvbG9yPWZhY3RvcihrcDE5OTEkY2x1c3RlcikpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKZzE5OTFwb2QgPC0gZzE5OTFwb2QgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDEsIGstUE9EIHdpdGggMjAlIG1pc3NpbmduZXNzIikKZzE5OTFwb2QKCmBgYAoKYGBge3IgZGF0YTFwb2QwLjN9CmRhdGExIDwtIGtwb2RjbHVzdHI6Om1ha2VEYXRhKHAgPSAyLCBuID0gMjAsIGsgPSAzLCBzaWdtYSA9IDAuMjUsIG1pc3NpbmcgPSAwLjMsIHNlZWQgPSAxOTkxKQpYbTE5OTEgPC0gZGF0YTFbWzJdXQprcDE5OTEgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTEsMykKCmZpdF9rcDE5OTFbM10gPC0ga3AxOTkxJGZpdAphcmlfa3AxOTkxWzNdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MSRjbHVzdGVyLCBrcDE5OTEkY2x1c3RlcikKCmcxOTkxcG9kIDwtIGdncGxvdChkYXRhID0gYXMuZGF0YS5mcmFtZShYMTk5MSksIG1hcHBpbmcgPSBhZXMoeD1YMTk5MVssMV0seT1YMTk5MVssMl0sIGNvbG9yPWZhY3RvcihrcDE5OTEkY2x1c3RlcikpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKZzE5OTFwb2QgPC0gZzE5OTFwb2QgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDEsIGstUE9EIHdpdGggMzAlIG1pc3NpbmduZXNzIikKZzE5OTFwb2QKYGBgCgpgYGB7ciBkYXRhMXBvZDAuNH0KZGF0YTEgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAyMCwgayA9IDMsIHNpZ21hID0gMC4yNSwgbWlzc2luZyA9IDAuNCwgc2VlZCA9IDE5OTEpCgpYbTE5OTEgPC0gZGF0YTFbWzJdXQprcDE5OTEgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTEsMykKCmZpdF9rcDE5OTFbNF0gPC0ga3AxOTkxJGZpdAphcmlfa3AxOTkxWzRdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MSRjbHVzdGVyLCBrcDE5OTEkY2x1c3RlcikKCmcxOTkxcG9kIDwtIGdncGxvdChkYXRhID0gYXMuZGF0YS5mcmFtZShYMTk5MSksIG1hcHBpbmcgPSBhZXMoeD1YMTk5MVssMV0seT1YMTk5MVssMl0sIGNvbG9yPWZhY3RvcihrcDE5OTEkY2x1c3RlcikpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKZzE5OTFwb2QgPC0gZzE5OTFwb2QgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDEsIGstUE9EIHdpdGggNDAlIG1pc3NpbmduZXNzIikKZzE5OTFwb2QKYGBgCgpgYGB7ciBkYXRhMXBvZDAuNX0KZGF0YTEgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAyMCwgayA9IDMsIHNpZ21hID0gMC4yNSwgbWlzc2luZyA9IDAuNSwgc2VlZCA9IDE5OTEpCgpYbTE5OTEgPC0gZGF0YTFbWzJdXQprcDE5OTEgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTEsMykKCmZpdF9rcDE5OTFbNV0gPC0ga3AxOTkxJGZpdAphcmlfa3AxOTkxWzVdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MSRjbHVzdGVyLCBrcDE5OTEkY2x1c3RlcikKCmcxOTkxcG9kIDwtIGdncGxvdChkYXRhID0gYXMuZGF0YS5mcmFtZShYMTk5MSksIG1hcHBpbmcgPSBhZXMoeD1YMTk5MVssMV0seT1YMTk5MVssMl0sIGNvbG9yPWZhY3RvcihrcDE5OTEkY2x1c3RlcikpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKZzE5OTFwb2QgPC0gZzE5OTFwb2QgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDEsIGstUE9EIHdpdGggNTAlIG1pc3NpbmduZXNzIikKZzE5OTFwb2QKYGBgCioqKgoKVGhlIGZpcnN0IGxpbmUgZ3JhcGggZGVtb25zdHJhdGVzIHRoZSBjaGFuZ2UgaW4gZml0IHZhbHVlIGFzIG1pc3NpbmduZXNzIGNoYW5nZXMuIFRoZSBibHVlIGxpbmUgcmVwcmVzZW50cyB0aGUgZml0IG9mIHRoZSBrLW1lYW5zIGNsdXN0ZXJpbmcuIAoKVGhlIHNlY29uZCBsaW5lIGdyYXBoIGRlbW9uc3RyYXRlcyB0aGUgY2hhbmdlIGluIEFSSSB2YWx1ZSBhcyBtaXNzaW5nbmVzcyBjaGFuZ2VzLiAKCmBgYHtyIGRhdGExbWV0cmljc30KbWlzc2luZ3BjdHMgPC0gYygwLjEsMC4yLDAuMywwLjQsMC41KQptZXRyaWNzX2xpc3QgPC0gY2JpbmQobWlzc2luZ3BjdHMsZml0X2twMTk5MSxhcmlfa3AxOTkxKQoKZzE5OTFwb2RmaXQgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKG1ldHJpY3NfbGlzdCksIG1hcHBpbmcgPSBhZXMoeD1taXNzaW5ncGN0cyx5PWZpdF9rcDE5OTEpKSArIGdlb21fbGluZSgpICsgZ2VvbV9wb2ludCgpICsgZ2VvbV9sYWJlbChhZXMobGFiZWwgPSByb3VuZChmaXRfa3AxOTkxLDQpKSwgbnVkZ2VfeSA9IC0wLjEpCmcxOTkxcG9kZml0IDwtIGcxOTkxcG9kZml0ICsgZ2VvbV9obGluZShtYXBwaW5nID0gYWVzKHlpbnRlcmNlcHQgPSBmaXRfa20xOTkxKSwgY29sb3IgPSAiYmx1ZSIpCmcxOTkxcG9kZml0IDwtIGcxOTkxcG9kZml0ICsgbGFicyh4ID0gIk1pc3NpbmduZXNzIiwgeSA9ICJGaXQiKSArIHlsaW0oMCwxKQpnMTk5MXBvZGZpdAoKZzE5OTFwb2RhcmkgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKG1ldHJpY3NfbGlzdCksIG1hcHBpbmcgPSBhZXMoeD1taXNzaW5ncGN0cyx5PWFyaV9rcDE5OTEpKSArIGdlb21fbGluZSgpICsgZ2VvbV9wb2ludCgpICsgZ2VvbV9sYWJlbChhZXMobGFiZWwgPSByb3VuZChhcmlfa3AxOTkxLDQpKSwgbnVkZ2VfeSA9IC0wLjEpCmcxOTkxcG9kYXJpIDwtIGcxOTkxcG9kYXJpICsgbGFicyh4ID0gIk1pc3NpbmduZXNzIiwgeSA9ICJBUkkiKSArIHlsaW0oMCwxKQpnMTk5MXBvZGFyaQoKYGBgCgoqKioKCiMjIyBEYXRhIDIKCioqKgoKRGF0YSAyIHBhcmFtZXRlcnM6IHAgPSAyLCBuID0gMTAwMCwgayA9IDMsIHNpZ21hID0gMC4yNSwgc2VlZCA9IDE5OTEKCkRhdGEgMiBpcyBhIGxhcmdlciBkYXRhIHNldCAoMTAwMCBvYnNlcnZhdGlvbnMpIHRoYW4gRGF0YSAxLiBXZSB3aWxsIGJlIGxvb2tpbmcgYXQ6CgotIGstbWVhbnMgcGVyZm9ybWFuY2Ugd2l0aCAwJSBtaXNzaW5nOyAKCi0gay1QT0QgcGVyZm9ybWFuY2Ugd2l0aCAxMCUgbWlzc2luZzsgCgotIGstUE9EIHBlcmZvcm1hbmNlIHdpdGggMjAlIG1pc3Npbmc7IAoKLSBrLVBPRCBwZXJmb3JtYW5jZSB3aXRoIDMwJSBtaXNzaW5nOyAKCi0gay1QT0QgcGVyZm9ybWFuY2Ugd2l0aCA0MCUgbWlzc2luZzsgCgotIGFuZCBrLVBPRCBwZXJmb3JtYW5jZSB3aXRoIDUwJSBtaXNzaW5nLgoKVGhleSBhcmUgZGVtb25zdHJhdGVkIGJ5IHRoZSBmb2xsb3dpbmcgc2NhdHRlciBwbG90cywgY29sb3JlZCBieSBjbHVzdGVyIGdyb3VwLiBCbGFjayBkb3RzIGluIHRoZSBrLW1lYW5zIHBsb3QgcmVwcmVzZW50cyB0aGUgY2x1c3RlciBjZW50ZXJzLiAKCioqKgoKYGBge3IgZGF0YTJtZWFuc30KZGF0YTIgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAxMDAwLCBrID0gMywgc2lnbWEgPSAwLjI1LCBtaXNzaW5nID0gMC4xLCBzZWVkID0gMTk5MSkKWDE5OTEgPC0gZGF0YTJbWzFdXQprbTE5OTEgPC0ga21lYW5zKFgxOTkxLDMpCgpmaXRfa20xOTkxIDwtIDEtKHN1bShrbTE5OTEkd2l0aGluc3MpL2ttMTk5MSR0b3RzcykKCmcxOTkxbWVhbnMgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKFgxOTkxKSwgbWFwcGluZyA9IGFlcyh4PVgxOTkxWywxXSx5PVgxOTkxWywyXSwgY29sb3I9ZmFjdG9yKGttMTk5MSRjbHVzdGVyKSkpICsgZ2VvbV9wb2ludCgpICsgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKSAKZzE5OTFtZWFucyA8LSBnMTk5MW1lYW5zICsgZ2VvbV9wb2ludChkYXRhID0gYXMuZGF0YS5mcmFtZShrbTE5OTEkY2VudGVycyksIG1hcHBpbmcgPSBhZXMoeD1rbTE5OTEkY2VudGVyc1ssMV0seT1rbTE5OTEkY2VudGVyc1ssMl0sIHNpemUgPSAzKSwgY29sb3IgPSAiYmxhY2siKQpnMTk5MW1lYW5zIDwtIGcxOTkxbWVhbnMgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDIsIGstbWVhbnMgd2l0aCBjb21wbGV0ZSBkYXRhIikKZzE5OTFtZWFucyAKYGBgCioqKgoKX19Db21tZW50X186IFRoaXMgZXhhbXBsZSBoYXBwZW5zIHRvIGRlbW9uc3RyYXRlIHRoZSBpbmNvbnNpc3RlbmNpZXMgaW4gay1tZWFucyBjbHVzdGVyaW5nIQoKKioqCgpgYGB7ciBkYXRhMnBvZDAuMX0KWG0xOTkxIDwtIGRhdGEyW1syXV0Ka3AxOTkxIDwtIGtwb2RjbHVzdHI6Omtwb2QoWG0xOTkxLDMpCgpmaXRfa3AxOTkxIDwtIHJlcCgwLDUpCmZpdF9rcDE5OTFbMV0gPC0ga3AxOTkxJGZpdAoKYXJpX2twMTk5MSA8LSByZXAoMCw1KQphcmlfa3AxOTkxWzFdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MSRjbHVzdGVyLCBrcDE5OTEkY2x1c3RlcikKZzE5OTFwb2QgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKFgxOTkxKSwgbWFwcGluZyA9IGFlcyh4PVgxOTkxWywxXSx5PVgxOTkxWywyXSwgY29sb3I9ZmFjdG9yKGtwMTk5MSRjbHVzdGVyKSkpICsgZ2VvbV9wb2ludCgpICsgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKQpnMTk5MXBvZCA8LSBnMTk5MXBvZCArIGxhYnMoeCA9ICJGZWF0dXJlIDEiLCB5ID0gIkZlYXR1cmUgMiIsIHRpdGxlID0gIkRhdGEgMiwgay1QT0Qgd2l0aCAxMCUgbWlzc2luZ25lc3MiKQpnMTk5MXBvZApgYGAKCmBgYHtyIGRhdGEycG9kMC4yfQpkYXRhMiA8LSBrcG9kY2x1c3RyOjptYWtlRGF0YShwID0gMiwgbiA9IDEwMDAsIGsgPSAzLCBzaWdtYSA9IDAuMjUsIG1pc3NpbmcgPSAwLjIsIHNlZWQgPSAxOTkxKQoKWG0xOTkxIDwtIGRhdGEyW1syXV0Ka3AxOTkxIDwtIGtwb2RjbHVzdHI6Omtwb2QoWG0xOTkxLDMpCgpmaXRfa3AxOTkxWzJdIDwtIGtwMTk5MSRmaXQKYXJpX2twMTk5MVsyXSA8LSBhZGoucmFuZC5pbmRleChrbTE5OTEkY2x1c3Rlciwga3AxOTkxJGNsdXN0ZXIpCgpnMTk5MXBvZCA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUoWDE5OTEpLCBtYXBwaW5nID0gYWVzKHg9WDE5OTFbLDFdLHk9WDE5OTFbLDJdLCBjb2xvcj1mYWN0b3Ioa3AxOTkxJGNsdXN0ZXIpKSkgKyBnZW9tX3BvaW50KCkgKyB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCmcxOTkxcG9kIDwtIGcxOTkxcG9kICsgbGFicyh4ID0gIkZlYXR1cmUgMSIsIHkgPSAiRmVhdHVyZSAyIiwgdGl0bGUgPSAiRGF0YSAyLCBrLVBPRCB3aXRoIDIwJSBtaXNzaW5nbmVzcyIpCmcxOTkxcG9kCmBgYAoKYGBge3IgZGF0YTJwb2QwLjN9CmRhdGEyIDwtIGtwb2RjbHVzdHI6Om1ha2VEYXRhKHAgPSAyLCBuID0gMTAwMCwgayA9IDMsIHNpZ21hID0gMC4yNSwgbWlzc2luZyA9IDAuMywgc2VlZCA9IDE5OTEpClhtMTk5MSA8LSBkYXRhMltbMl1dCmtwMTk5MSA8LSBrcG9kY2x1c3RyOjprcG9kKFhtMTk5MSwzKQoKZml0X2twMTk5MVszXSA8LSBrcDE5OTEkZml0CmFyaV9rcDE5OTFbM10gPC0gYWRqLnJhbmQuaW5kZXgoa20xOTkxJGNsdXN0ZXIsIGtwMTk5MSRjbHVzdGVyKQoKZzE5OTFwb2QgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKFgxOTkxKSwgbWFwcGluZyA9IGFlcyh4PVgxOTkxWywxXSx5PVgxOTkxWywyXSwgY29sb3I9ZmFjdG9yKGtwMTk5MSRjbHVzdGVyKSkpICsgZ2VvbV9wb2ludCgpICsgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKQpnMTk5MXBvZCA8LSBnMTk5MXBvZCArIGxhYnMoeCA9ICJGZWF0dXJlIDEiLCB5ID0gIkZlYXR1cmUgMiIsIHRpdGxlID0gIkRhdGEgMiwgay1QT0Qgd2l0aCAzMCUgbWlzc2luZ25lc3MiKQpnMTk5MXBvZApgYGAKCmBgYHtyIGRhdGEycG9kMC40fQpkYXRhMiA8LSBrcG9kY2x1c3RyOjptYWtlRGF0YShwID0gMiwgbiA9IDEwMDAsIGsgPSAzLCBzaWdtYSA9IDAuMjUsIG1pc3NpbmcgPSAwLjQsIHNlZWQgPSAxOTkxKQoKWG0xOTkxIDwtIGRhdGEyW1syXV0Ka3AxOTkxIDwtIGtwb2RjbHVzdHI6Omtwb2QoWG0xOTkxLDMpCgpmaXRfa3AxOTkxWzRdIDwtIGtwMTk5MSRmaXQKYXJpX2twMTk5MVs0XSA8LSBhZGoucmFuZC5pbmRleChrbTE5OTEkY2x1c3Rlciwga3AxOTkxJGNsdXN0ZXIpCgpnMTk5MXBvZCA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUoWDE5OTEpLCBtYXBwaW5nID0gYWVzKHg9WDE5OTFbLDFdLHk9WDE5OTFbLDJdLCBjb2xvcj1mYWN0b3Ioa3AxOTkxJGNsdXN0ZXIpKSkgKyBnZW9tX3BvaW50KCkgKyB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCmcxOTkxcG9kIDwtIGcxOTkxcG9kICsgbGFicyh4ID0gIkZlYXR1cmUgMSIsIHkgPSAiRmVhdHVyZSAyIiwgdGl0bGUgPSAiRGF0YSAyLCBrLVBPRCB3aXRoIDQwJSBtaXNzaW5nbmVzcyIpCmcxOTkxcG9kCmBgYAoKYGBge3IgZGF0YTJwb2QwLjV9CmRhdGEyIDwtIGtwb2RjbHVzdHI6Om1ha2VEYXRhKHAgPSAyLCBuID0gMTAwMCwgayA9IDMsIHNpZ21hID0gMC4yNSwgbWlzc2luZyA9IDAuNSwgc2VlZCA9IDE5OTEpCgpYbTE5OTEgPC0gZGF0YTJbWzJdXQprcDE5OTEgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTEsMykKCmZpdF9rcDE5OTFbNV0gPC0ga3AxOTkxJGZpdAphcmlfa3AxOTkxWzVdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MSRjbHVzdGVyLCBrcDE5OTEkY2x1c3RlcikKCmcxOTkxcG9kIDwtIGdncGxvdChkYXRhID0gYXMuZGF0YS5mcmFtZShYMTk5MSksIG1hcHBpbmcgPSBhZXMoeD1YMTk5MVssMV0seT1YMTk5MVssMl0sIGNvbG9yPWZhY3RvcihrcDE5OTEkY2x1c3RlcikpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKZzE5OTFwb2QgPC0gZzE5OTFwb2QgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDIsIGstUE9EIHdpdGggNTAlIG1pc3NpbmduZXNzIikKZzE5OTFwb2QKYGBgCioqKgoKVGhlIGZpcnN0IGxpbmUgZ3JhcGggZGVtb25zdHJhdGVzIHRoZSBjaGFuZ2UgaW4gZml0IHZhbHVlIGFzIG1pc3NpbmduZXNzIGNoYW5nZXMuIFRoZSBibHVlIGxpbmUgcmVwcmVzZW50cyB0aGUgZml0IG9mIHRoZSBrLW1lYW5zIGNsdXN0ZXJpbmcuIAoKVGhlIHNlY29uZCBsaW5lIGdyYXBoIGRlbW9uc3RyYXRlcyB0aGUgY2hhbmdlIGluIEFSSSB2YWx1ZSBhcyBtaXNzaW5nbmVzcyBjaGFuZ2VzLiAKCioqKgoKYGBge3IgZGF0YTJtZXRyaWNzfQptaXNzaW5ncGN0cyA8LSBjKDAuMSwwLjIsMC4zLDAuNCwwLjUpCm1ldHJpY3NfbGlzdCA8LSBjYmluZChtaXNzaW5ncGN0cyxmaXRfa3AxOTkxLGFyaV9rcDE5OTEpCgpnMTk5MXBvZGZpdCA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUobWV0cmljc19saXN0KSwgbWFwcGluZyA9IGFlcyh4PW1pc3NpbmdwY3RzLHk9Zml0X2twMTk5MSkpICsgZ2VvbV9saW5lKCkgKyBnZW9tX3BvaW50KCkgKyBnZW9tX2xhYmVsKGFlcyhsYWJlbCA9IHJvdW5kKGZpdF9rcDE5OTEsNCkpLCBudWRnZV95ID0gLTAuMSkKZzE5OTFwb2RmaXQgPC0gZzE5OTFwb2RmaXQgKyBnZW9tX2hsaW5lKG1hcHBpbmcgPSBhZXMoeWludGVyY2VwdCA9IGZpdF9rbTE5OTEpLCBjb2xvciA9ICJibHVlIikKZzE5OTFwb2RmaXQgPC0gZzE5OTFwb2RmaXQgKyBsYWJzKHggPSAiTWlzc2luZ25lc3MiLCB5ID0gIkZpdCIpICsgeWxpbSgwLDEpCmcxOTkxcG9kZml0CgpnMTk5MXBvZGFyaSA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUobWV0cmljc19saXN0KSwgbWFwcGluZyA9IGFlcyh4PW1pc3NpbmdwY3RzLHk9YXJpX2twMTk5MSkpICsgZ2VvbV9saW5lKCkgKyBnZW9tX3BvaW50KCkgKyBnZW9tX2xhYmVsKGFlcyhsYWJlbCA9IHJvdW5kKGFyaV9rcDE5OTEsNCkpLCBudWRnZV95ID0gLTAuMSkKZzE5OTFwb2RhcmkgPC0gZzE5OTFwb2RhcmkgKyBsYWJzKHggPSAiTWlzc2luZ25lc3MiLCB5ID0gIkFSSSIpICsgeWxpbSgwLDEpCmcxOTkxcG9kYXJpCmBgYAoKKioqCgpfX0NvbW1lbnRfXzogQmVjYXVzZSBvZiB0aGUgaW5jb25zaXN0ZW50IGstbWVhbnMgY2x1c3RlcmluZywgd2UgaGF2ZSBhIGxvdyBmaXQgc2NvcmUgZm9yIHRoZSBrLW1lYW5zIGNsdXN0ZXJpbmcgKGJsdWUgbGluZSkuIFdlIGFsc28gaGF2ZSBsb3cgQVJJIHNjb3JlcyBiZWNhdXNlIG9mIHRoZSBkcmFzdGljIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgay1tZWFucyBjbHVzdGVyaW5nIGFuZCB0aGUgay1QT0QgY2x1c3RlcmluZ3MuIAoKKioqCgojIyMgRGF0YSAzCgoqKioKCkRhdGEgMyBwYXJhbWV0ZXJzOiBwID0gMiwgbiA9IDIwMDAsIGsgPSA1LCBzaWdtYSA9IDAuMjUsIHNlZWQgPSAxOTkyCgpEYXRhIDMgKDIwMDAgb2JzZXJ2YXRpb25zKSBpcyB0d2ljZSB0aGUgc2l6ZSBvZiBEYXRhIDIgYW5kIG9ic2VydmF0aW9ucyBhcmUgY2x1c3RlcmVkIGludG8gNSBjbHVzdGVycywgaW5zdGVhZCBvZiAzLiBUaGUgY2hhbmdlIHNpZ21hIHNpZ25pZmllcyBhbiBpbmNyZWFzZSBpbiB0aGUgc3ByZWFkIG9mIG9ic2VydmF0aW9ucyBhcm91bmQgaXRzIGNsdXN0ZXIgY2VudGVyLiAKCioqKgoKYGBge3IgZGF0YTNtZWFuc30KZGF0YTMgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAyMDAwLCBrID0gNSwgc2lnbWEgPSAwLjUsIG1pc3NpbmcgPSAwLjEsIHNlZWQgPSAxOTkyKQpYMTk5MiA8LSBkYXRhM1tbMV1dCmttMTk5MiA8LSBrbWVhbnMoWDE5OTIsNSkKCmZpdF9rbTE5OTIgPC0gMS0oc3VtKGttMTk5MiR3aXRoaW5zcykva20xOTkyJHRvdHNzKQoKZzE5OTJtZWFucyA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUoWDE5OTIpLCBtYXBwaW5nID0gYWVzKHg9WDE5OTJbLDFdLHk9WDE5OTJbLDJdLCBjb2xvcj1mYWN0b3Ioa20xOTkyJGNsdXN0ZXIpKSkgKyBnZW9tX3BvaW50KCkgKyB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpIApnMTk5Mm1lYW5zIDwtIGcxOTkybWVhbnMgKyBnZW9tX3BvaW50KGRhdGEgPSBhcy5kYXRhLmZyYW1lKGttMTk5MiRjZW50ZXJzKSwgbWFwcGluZyA9IGFlcyh4PWttMTk5MiRjZW50ZXJzWywxXSx5PWttMTk5MiRjZW50ZXJzWywyXSwgc2l6ZSA9IDMpLCBjb2xvciA9ICJibGFjayIpCmcxOTkybWVhbnMgPC0gZzE5OTJtZWFucyArIGxhYnMoeCA9ICJGZWF0dXJlIDEiLCB5ID0gIkZlYXR1cmUgMiIsIHRpdGxlID0gIkRhdGEgMywgay1tZWFucyB3aXRoIGNvbXBsZXRlIGRhdGEiKQpnMTk5Mm1lYW5zIApgYGAKCmBgYHtyIGRhdGEzcG9kMC4xfQpYbTE5OTIgPC0gZGF0YTNbWzJdXQprcDE5OTIgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTIsNSkKCmZpdF9rcDE5OTIgPC0gcmVwKDAsNSkKZml0X2twMTk5MlsxXSA8LSBrcDE5OTIkZml0Cgphcmlfa3AxOTkyIDwtIHJlcCgwLDUpCmFyaV9rcDE5OTJbMV0gPC0gYWRqLnJhbmQuaW5kZXgoa20xOTkyJGNsdXN0ZXIsIGtwMTk5MiRjbHVzdGVyKQpnMTk5MnBvZCA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUoWDE5OTIpLCBtYXBwaW5nID0gYWVzKHg9WDE5OTJbLDFdLHk9WDE5OTJbLDJdLCBjb2xvcj1mYWN0b3Ioa3AxOTkyJGNsdXN0ZXIpKSkgKyBnZW9tX3BvaW50KCkgKyB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCmcxOTkycG9kIDwtIGcxOTkycG9kICsgbGFicyh4ID0gIkZlYXR1cmUgMSIsIHkgPSAiRmVhdHVyZSAyIiwgdGl0bGUgPSAiRGF0YSAzLCBrLVBPRCB3aXRoIDEwJSBtaXNzaW5nbmVzcyIpCmcxOTkycG9kCmBgYApgYGB7ciBkYXRhM3BvZDAuMn0KZGF0YTMgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAyMDAwLCBrID0gNSwgc2lnbWEgPSAwLjI1LCBtaXNzaW5nID0gMC4yLCBzZWVkID0gMTk5MikKClhtMTk5MiA8LSBkYXRhM1tbMl1dCmtwMTk5MiA8LSBrcG9kY2x1c3RyOjprcG9kKFhtMTk5Miw1KQoKZml0X2twMTk5MlsyXSA8LSBrcDE5OTIkZml0CmFyaV9rcDE5OTJbMl0gPC0gYWRqLnJhbmQuaW5kZXgoa20xOTkyJGNsdXN0ZXIsIGtwMTk5MiRjbHVzdGVyKQoKZzE5OTJwb2QgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKFgxOTkyKSwgbWFwcGluZyA9IGFlcyh4PVgxOTkyWywxXSx5PVgxOTkyWywyXSwgY29sb3I9ZmFjdG9yKGtwMTk5MiRjbHVzdGVyKSkpICsgZ2VvbV9wb2ludCgpICsgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKQpnMTk5MnBvZCA8LSBnMTk5MnBvZCArIGxhYnMoeCA9ICJGZWF0dXJlIDEiLCB5ID0gIkZlYXR1cmUgMiIsIHRpdGxlID0gIkRhdGEgMywgay1QT0Qgd2l0aCAyMCUgbWlzc2luZ25lc3MiKQpnMTk5MnBvZApgYGAKYGBge3IgZGF0YTNwb2QwLjN9CmRhdGEzIDwtIGtwb2RjbHVzdHI6Om1ha2VEYXRhKHAgPSAyLCBuID0gMjAwMCwgayA9IDUsIHNpZ21hID0gMC4yNSwgbWlzc2luZyA9IDAuMywgc2VlZCA9IDE5OTIpCgpYbTE5OTIgPC0gZGF0YTNbWzJdXQprcDE5OTIgPC0ga3BvZGNsdXN0cjo6a3BvZChYbTE5OTIsNSkKCmZpdF9rcDE5OTJbM10gPC0ga3AxOTkyJGZpdAphcmlfa3AxOTkyWzNdIDwtIGFkai5yYW5kLmluZGV4KGttMTk5MiRjbHVzdGVyLCBrcDE5OTIkY2x1c3RlcikKCmcxOTkycG9kIDwtIGdncGxvdChkYXRhID0gYXMuZGF0YS5mcmFtZShYMTk5MiksIG1hcHBpbmcgPSBhZXMoeD1YMTk5MlssMV0seT1YMTk5MlssMl0sIGNvbG9yPWZhY3RvcihrcDE5OTIkY2x1c3RlcikpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKZzE5OTJwb2QgPC0gZzE5OTJwb2QgKyBsYWJzKHggPSAiRmVhdHVyZSAxIiwgeSA9ICJGZWF0dXJlIDIiLCB0aXRsZSA9ICJEYXRhIDMsIGstUE9EIHdpdGggMzAlIG1pc3NpbmduZXNzIikKZzE5OTJwb2QKYGBgCmBgYHtyIGRhdGEzcG9kMC40fQpkYXRhMyA8LSBrcG9kY2x1c3RyOjptYWtlRGF0YShwID0gMiwgbiA9IDIwMDAsIGsgPSA1LCBzaWdtYSA9IDAuMjUsIG1pc3NpbmcgPSAwLjQsIHNlZWQgPSAxOTkyKQoKWG0xOTkyIDwtIGRhdGEzW1syXV0Ka3AxOTkyIDwtIGtwb2RjbHVzdHI6Omtwb2QoWG0xOTkyLDUpCgpmaXRfa3AxOTkyWzRdIDwtIGtwMTk5MiRmaXQKYXJpX2twMTk5Mls0XSA8LSBhZGoucmFuZC5pbmRleChrbTE5OTIkY2x1c3Rlciwga3AxOTkyJGNsdXN0ZXIpCgpnMTk5MnBvZCA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUoWDE5OTIpLCBtYXBwaW5nID0gYWVzKHg9WDE5OTJbLDFdLHk9WDE5OTJbLDJdLCBjb2xvcj1mYWN0b3Ioa3AxOTkyJGNsdXN0ZXIpKSkgKyBnZW9tX3BvaW50KCkgKyB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCmcxOTkycG9kIDwtIGcxOTkycG9kICsgbGFicyh4ID0gIkZlYXR1cmUgMSIsIHkgPSAiRmVhdHVyZSAyIiwgdGl0bGUgPSAiRGF0YSAzLCBrLVBPRCB3aXRoIDQwJSBtaXNzaW5nbmVzcyIpCmcxOTkycG9kCmBgYApgYGB7ciBkYXRhM3BvZDAuNX0KZGF0YTMgPC0ga3BvZGNsdXN0cjo6bWFrZURhdGEocCA9IDIsIG4gPSAyMDAwLCBrID0gNSwgc2lnbWEgPSAwLjI1LCBtaXNzaW5nID0gMC41LCBzZWVkID0gMTk5MikKClhtMTk5MiA8LSBkYXRhM1tbMl1dCmtwMTk5MiA8LSBrcG9kY2x1c3RyOjprcG9kKFhtMTk5Miw1KQoKZml0X2twMTk5Mls1XSA8LSBrcDE5OTIkZml0CmFyaV9rcDE5OTJbNV0gPC0gYWRqLnJhbmQuaW5kZXgoa20xOTkyJGNsdXN0ZXIsIGtwMTk5MiRjbHVzdGVyKQoKZzE5OTJwb2QgPC0gZ2dwbG90KGRhdGEgPSBhcy5kYXRhLmZyYW1lKFgxOTkyKSwgbWFwcGluZyA9IGFlcyh4PVgxOTkyWywxXSx5PVgxOTkyWywyXSwgY29sb3I9ZmFjdG9yKGtwMTk5MiRjbHVzdGVyKSkpICsgZ2VvbV9wb2ludCgpICsgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKQpnMTk5MnBvZCA8LSBnMTk5MnBvZCArIGxhYnMoeCA9ICJGZWF0dXJlIDEiLCB5ID0gIkZlYXR1cmUgMiIsIHRpdGxlID0gIkRhdGEgMywgay1QT0Qgd2l0aCA1MCUgbWlzc2luZ25lc3MiKQpnMTk5MnBvZApgYGAKCioqKgoKVGhlIGZpcnN0IGxpbmUgZ3JhcGggZGVtb25zdHJhdGVzIHRoZSBjaGFuZ2UgaW4gZml0IHZhbHVlIGFzIG1pc3NpbmduZXNzIGNoYW5nZXMuIFRoZSBibHVlIGxpbmUgcmVwcmVzZW50cyB0aGUgZml0IG9mIHRoZSBrLW1lYW5zIGNsdXN0ZXJpbmcuIAoKVGhlIHNlY29uZCBsaW5lIGdyYXBoIGRlbW9uc3RyYXRlcyB0aGUgY2hhbmdlIGluIEFSSSB2YWx1ZSBhcyBtaXNzaW5nbmVzcyBjaGFuZ2VzLiAKCioqKgoKYGBge3IgZGF0YTNtZXRyaWNzfQptaXNzaW5ncGN0cyA8LSBjKDAuMSwwLjIsMC4zLDAuNCwwLjUpCm1ldHJpY3NfbGlzdCA8LSBjYmluZChtaXNzaW5ncGN0cyxmaXRfa3AxOTkyLGFyaV9rcDE5OTIpCgpnMTk5MnBvZGZpdCA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUobWV0cmljc19saXN0KSwgbWFwcGluZyA9IGFlcyh4PW1pc3NpbmdwY3RzLHk9Zml0X2twMTk5MikpICsgZ2VvbV9saW5lKCkgKyBnZW9tX3BvaW50KCkgKyBnZW9tX2xhYmVsKGFlcyhsYWJlbCA9IHJvdW5kKGZpdF9rcDE5OTIsNCkpLCBudWRnZV95ID0gMC4wNSkKZzE5OTJwb2RmaXQgPC0gZzE5OTJwb2RmaXQgKyBnZW9tX2hsaW5lKG1hcHBpbmcgPSBhZXMoeWludGVyY2VwdCA9IGZpdF9rbTE5OTIpLCBjb2xvciA9ICJibHVlIikKZzE5OTJwb2RmaXQgPC0gZzE5OTJwb2RmaXQgKyBsYWJzKHggPSAiTWlzc2luZ25lc3MiLCB5ID0gIkZpdCIpICsgeWxpbSgwLDEpCmcxOTkycG9kZml0CgpnMTk5MnBvZGFyaSA8LSBnZ3Bsb3QoZGF0YSA9IGFzLmRhdGEuZnJhbWUobWV0cmljc19saXN0KSwgbWFwcGluZyA9IGFlcyh4PW1pc3NpbmdwY3RzLHk9YXJpX2twMTk5MikpICsgZ2VvbV9saW5lKCkgKyBnZW9tX3BvaW50KCkgKyBnZW9tX2xhYmVsKGFlcyhsYWJlbCA9IHJvdW5kKGFyaV9rcDE5OTIsNCkpLCBudWRnZV95ID0gLTAuMSkKZzE5OTJwb2RhcmkgPC0gZzE5OTJwb2RhcmkgKyBsYWJzKHggPSAiTWlzc2luZ25lc3MiLCB5ID0gIkFSSSIpICsgeWxpbSgwLDEpCmcxOTkycG9kYXJpCmBgYAoKKioqCgojIyMgUGxvdHMgZXhwbGFpbmVkCgoqKioKCkFzIHByZXZpb3VzbHkgbWVudGlvbmVkLCB0aGUgc2NhdHRlciBwbG90cyBmb3Igay1QT0QgcGVyZm9ybWFuY2Ugd2lsbCBpbmNsdWRlIGFsbCBvYnNlcnZhdGlvbnMgaW4gdGhlIGNvbXBsZXRlIGRhdGEgbGlrZSB0aGUgcGxvdHMgZm9yIGstbWVhbnMsIGJlY2F1c2UgdGhlIHBvaW50IG9mIGstUE9EIGlzIHRvIHBlcmZvcm0gY2x1c3RlcmluZyBvbiBhbGwgdGhlIG9ic2VydmF0aW9ucyBpbmNsdWRpbmcgdGhvc2Ugd2l0aCBtaXNzaW5nIGZlYXR1cmVzLiBIb3dldmVyLCBpbiBrLVBPRCwgdGhvc2UgbWlzc2luZyBmZWF0dXJlcyB3aWxsIGJlIGFzc2lnbmVkIHZhbHVlcyBhbmQgdXBkYXRlZCB0aHJvdWdob3V0IGl0ZXJhdGlvbnMsIHdoaWNoIGFyZSBub3QgbGlrZWx5IHRoZSBzYW1lIHZhbHVlcyBhcyB0aGUgb25lcyBpbiB0aGUgY29tcGxldGUgZGF0YS4gVGhpcyBleHBsYWlucyB3aHkgZXZlbiB0aG91Z2ggdGhlIGstUE9EIGNsdXN0ZXJpbmcgc2NhdHRlciBwbG90cyBtYXkgbG9vayB3b3JzZSB0aGFuIHRoZSBrLW1lYW5zIHNjYXR0ZXIgcGxvdCwgYnV0IGstUE9EIHRlbmQgdG8gaGF2ZSBiZXR0ZXIgdmFsdWVzIGZvciB0aGUgZml0IG1ldHJpYy4gCgpGcm9tIHRoZSBnZW5lcmF0ZWQgbGluZSBwbG90cyBtZWFzdXJpbmcgdGhlIGZpdCBhbmQgQVJJIG1ldHJpY3Mgb2Ygay1wb2QgY2x1c3RlcmluZyBjb21wYXJlZCB0byBrLW1lYW5zIGNsdXN0ZXJpbmcsIHdlIGNhbiBjb25jbHVkZTogay1QT0QgaXMgbW9yZSBjb25zaXN0ZW50IF9fd2hlbiBkYXRhIGlzIGxhcmdlcl9fLiBJbiBhZGRpdGlvbiwgd2hlbiBkYXRhIGlzIGxhcmdlciwgaXQgaXMgbW9yZSBvYnZpb3VzIHRoYXQgX190aGUgaGlnaGVyIHRoZSBtaXNzaW5nbmVzcywgdGhlIGxvd2VyIHRoZSBBUklfXywgd2hpY2ggbWVhbnMgay1QT0QgY2x1c3RlcmluZyBkaXNwbGF5cyBtb3JlIGRldmlhdGlvbiB0aGFuIGstbWVhbnMgY2x1c3RlcmluZyBhcyBtaXNzaW5nbmVzcyBpbmNyZWFzZXMuIFdlIGFsc28gbm90aWNlIHRoYXQgay1QT0QgcGVyZm9ybWFuY2UgaXMgbm90IGdyZWF0bHkgYWZmZWN0ZWQgYnkgaW5jcmVhc2luZyB0aGUgbWlzc2luZ25lc3Mgd2l0aGluIHRoZSBkYXRhLgoKVGhlc2UgcGVyZm9ybWFuY2UgYW5hbHlzaXMgZG8gbm90IGRlbW9uc3RyYXRlIGstUE9EJ3MgZmFzdCBleGVjdXRpb24gdGltZS4gRGV0YWlsZWQgZGlzY3Vzc2lvbiBhYm91dCBhdHRyaWJ1dGVzIG9mIGstUE9EIGNsdXN0ZXJpbmcgcGxlYXNlIHJlZmVyIHRvICJrLVBPRDogQSBNZXRob2QgZm9yIGstTWVhbnMgQ2x1c3RlcmluZyBvZiBNaXNzaW5nIERhdGEiIGJ5IEpvY2VseW4gVC4gQ2hpLCBFcmljIEMuIENoaSAmIFJpY2hhcmQgRy4gQmFyYW5pdWsuIAoKKioq